#include "Heap.h"

heap::heap(int k) {
	if (!k) k = 1;
	_size = 0;
	capacity = k;
	hpData = (HPDatatype*)malloc(k * sizeof HPDatatype);
	if (hpData == nullptr) {
		perror("malloc fail");
		return;
	}
}

heap::~heap() {
	assert(hpData);

	free(hpData);
}

void heap::AdjustUp(int * _data, int x) {
	assert(_data);

	while (x > 0 && _data[(x - 1) >> 1] < _data[x]) {
		swap(_data[(x - 1) >> 1], _data[x]);
		x = (x - 1) >> 1;
	}
}

void heap::AdjustDown(int* _data, int x, int n) {
	assert(_data);

	int child = (x << 1) + 1;
	while (child < n) {
		if (child + 1 < n && _data[child] < _data[child + 1])
			child++;
		if (_data[x] < _data[child])
			swap(_data[x], _data[child]);
		else
			break;
		x = child;
		child = (x << 1) + 1;
	}
}

bool heap::empty() {
	assert(hpData);

	return !_size;
}

void heap::expand() {
	assert(hpData);

	HPDatatype* rlc = (HPDatatype*)realloc(hpData, sizeof HPDatatype * capacity * 2);
	if (rlc == nullptr) {
		perror("realloc fail");
		return;
	}
	hpData = rlc;
	capacity *= 2;
}

void heap::push(HPDatatype x) {
	assert(hpData);

	if (_size == capacity)
		expand();
	hpData[_size] = x;
	AdjustUp(hpData, _size++);
}

void heap::pop() {
	assert(hpData);
	assert(!empty());

	_size--;
	swap(hpData[0], hpData[_size]);
	AdjustDown(hpData, 0, _size);
}

int heap::size() {
	assert(hpData);

	return _size;
}

HPDatatype heap::top() {
	assert(hpData);
	if (empty())
		return -1;

	return hpData[0];
}

void HeapSort(int* st, int* ed) {
	int n = ed - st;
	for (int i = (n - 2) >> 1; i >= 0; i--) {
		heap::AdjustDown(st, i, n);
	}

	for (int i = n - 1; i > 0; i--) {
		swap(st[0], st[i]);
		heap::AdjustDown(st, 0, i);
	}
}